package Leetcode;

/**
 * @Author piper
 * @Date 2019/10/23 9:20 上午
 */
public class 力扣69_x的平方根 {

    /**
     * 自己写的 暴力法，逐个递加法
     * 如果数字很大，那么循环次数必将会很大
     */
    static int mySqrt(int x) {
        long l = 0;
        while (true) {
            long a = l * l;
            if (a > x) {
                return (int) l - 1;
            } else if (a == x) {
                return (int) l;
            }
            l++;
        }
    }

    /**
     * 二分查找法
     */
    static int mySqrt1(int x) {
        //l左边界 r右边界+1是为了照顾1
        long l = 0, r = x / 2 + 1;
        while (l < r) { //11
            //+1取右边中位数 防止x=8 l=2 r=3死循环
            //11，22，33 三个条件相辅相成
            long m = (r + l + 1) / 2; //22
            long c = m * m;
            if (c > x) {
                //防止死循环 m-1是为了有机会让r==l以退出循环
                r = m - 1; //33
            } else if (c <= x) {
                l = m;
            }
        }
        return (int) l;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt1(1));
        System.out.println(mySqrt1(8));
        System.out.println(mySqrt1(2147483647));
    }
}
